package dataStructure.chapter06_树.part1二叉树.binarysearchtree2;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author https://gitee.com/W_Jun
 * @date 2022-03-09 14:09
 * @Description 二叉树的四种遍历-适用于所有二叉树，不只是二叉搜索树
 *              遍历的应用1：计算二叉树的高度-递归，迭代(利用层序遍历)两种方法实现
 *              遍历的应用2：判断一棵树是否为完全二叉树-利用层序遍历
 *              遍历的应用3：反转二叉树-四种遍历均可实现
 */
public class BinarySearchTree<E> {
    private int size;
    private Node<E> root;//根节点
    private Comparator<E> comparator;

    public BinarySearchTree(Comparator comparator) {
        this.comparator = comparator;
    }

    public BinarySearchTree() {
        this(null);
    }

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
        //判断节点是否为叶子节点.在判断树是否完全二叉树的时候会用到
        public boolean isLeaf() {
            return left == null && right == null;
        }
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
    }

    /*
     * 添加元素的话，不能添加null，定义这个方法用来检查添加的element是否为空
     * */
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    /*
     * 返回值等于0代表e1与e2相等；大于0代表e1大于e2
     * */
    private int compare(E e1, E e2) {
        //比较器不为null。
        if (comparator != null) {
            //System.out.println("test-调用了comparator比较器");
            return comparator.compare(e1, e2);
        }
        //比较器如果是null，强制使用Comparable接口进行比较
        //System.out.println("test-实现了Comparable接口");
        return ((Comparable<E>)e1).compareTo(e2);
    }

    /**
     * 元素数量
     * */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空
     * */
    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 添加元素
     * */
    public void add(E element) {
        elementNotNullCheck(element);
        //添加的是第一个节点
        if (root == null) {
            root = new Node<E>(element, null);
            size++;
            return;
        }

        //添加的不是第一个节点, 需要先找到父节点，然后在父节点的下面插入新节点
        //找到父节点
        Node<E> node = root;//创建新节点
        Node<E> parent = root;
        int cmp = 0;//需要记录最后一次的值，用以判断添加的节点在父节点的左还是右
        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                //新元素element比当前结点的值大，
                //就让element与当前结点的右子结点进行比较,直到当前结点的右子节点为空时跳出循环
                //这时，父节点正是要插入的新节点的父节点
                node = node.right;
            }else if (cmp < 0) {
                node = node.left;
            }else {
                node.element = element;//相等就进行值的覆盖
            }
        }

        //看看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.right =newNode;
        }else {
            parent.left = newNode;
        }
        size++;
    }

    /**
     * 递归实现前序遍历，逻辑写死——打印
     * */
    public void preorderTraversal() {
        preorderTraversal(root);
    }
    public void preorderTraversal(Node<E> node) {
        if (node ==null) return;
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    /**
     * 递归实现中序遍历，逻辑写死——打印
     * */
    public void inorderTraversal() {
        inorderTraversal(root);
    }
    public void inorderTraversal(Node<E> node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);
    }

    /**
     * 递归实现后序遍历，逻辑写死——打印
     * */
    public void postorderTraversal() {
        postorderTraversal(root);
    }
    public void postorderTraversal(Node<E> node) {
        if (node == null) return;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.element);
    }

    /**
     * 用队列实现层序遍历，逻辑写死——打印
     * */
    public void levelOrderTraversal() {
        if (root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        //代码能执行到这里，说明root不为空，将root入队
        queue.offer(root);
        while(!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.element);
            //队列非空，就获取队头节点即出队操作，并判断其左右子节点是否为空
            if (node.left != null) {
                //左子节点非空，就入队
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    //为了遍历访问时候，不将逻辑写死，实现的时候再具体写，定义一个遍历接口
    public static interface Visitor<E> {
        void visit(E element);
    }
    /**
     * 用队列实现层序遍历，逻辑不写死，在使用的时候实现
     * */
    public void levelOrder(Visitor<E> visitor) {
        if (root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //System.out.println(node.element);
            visitor.visit(node.element);//真正的逻辑在用的时候具体实现
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 递归实现前序遍历，具体逻辑具体实现
     * */
    public void preorder(Visitor<E> visitor) {
        preorder(root,visitor);
    }
    public void preorder(Node<E> node, Visitor<E> visitor) {
        if (node== null || visitor == null) return;
        visitor.visit(node.element);
        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }

    /**
     * 递归实现中序遍历，具体逻辑具体实现
     * */
    public void inorder(Visitor<E> visitor) {
        inorder(root,visitor);
    }
    public void inorder(Node<E> node, Visitor<E> visitor) {
        if (node== null || visitor == null) return;
        inorder(node.left, visitor);
        visitor.visit(node.element);
        inorder(node.right, visitor);
    }

    /**
     * 递归实现后序遍历，具体逻辑具体实现
     * */
    public void postorder(Visitor<E> visitor) {
        postorder(root,visitor);
    }
    public void postorder(Node<E> node, Visitor<E> visitor) {
        if (node== null || visitor == null) return;
        postorder(node.left, visitor);
        postorder(node.right, visitor);
        visitor.visit(node.element);
    }

    /**
     * 实现二叉树的简单树形结构打印-涉及前序遍历的思想
     * */
    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        toString(root, str, "");
        return str.toString();
    }
    public void toString(Node<E> node, StringBuilder str, String prefix) {
        if (node == null) return;
        str.append(prefix).append(node.element).append("\n");
        toString(node.left, str, prefix + "L---");
        toString(node.right, str, prefix + "R---");
    }

    /**
     * 计算二叉树的高度,递归
     * */
    public int height() {
        return height(root);
    }
    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * 计算二叉树高度，迭代，利用层序遍历
     * */
    public int high() {
        if (root == null) return 0;
        int height = 0;
        //levelSize存储每一层元素数量，默认要访问根节点，初始值就是1个，只有根
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //每取出一个元素，当前层的元素个数就减去1
            levelSize--;
            //System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            //每访问完一层，当前层的元素个数就是0；队列中的元素个数就是:下一层的size
            if (levelSize == 0) {//意味着即将访问下一层
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    /**
    * 判断是否为完全二叉树
    * 优化的写法，左右分开判断（按照层序遍历的框架写）
    * */
    public boolean isComplete() {
        if (root == null) return false;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();

            //如果是完全二叉树，遇到node.right==null,后面的节点一定是叶子节点
            if (leaf && !node.isLeaf()) return false;//要求是叶子，但实际不是叶子，返回false

            //左
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                //node.left = null && node.right != null的情况
                return false;
            }

            //右
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                //node.right == null的情况（左边可能空也可不空），
                //后边的结点必须要求都是叶子节点才是完全二叉树
                leaf = true;
            }
        }
        return true;
    }
    /*
    一种比较复杂的写法，左空、右空、左不空、右不空，两两组合有四种情况分别考虑
    public boolean isComplete() {
        if (root == null) return false;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;//如果执行了else中的代码之后，leaf就是true了

            if (node.left != null && node.right != null) {//这个情况下入队的只有左右都有子树的结点的子结点
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                return false;
            } else {//node.left!=node && node.right==null或者node.left==null && node.right==null的情况
                //后面遍历的节点必须是叶子节点,才为完全二叉树
                leaf = true;
                if (node.left != null){
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }*/

    /**
     * 翻转二叉树,就是把所有节点的左右子树交换,前序实现（前、中、后、层 都可以实现）
     * */
    public  Node<E> invertTree() {
        return invertTree(root);
    }
    private Node<E> invertTree(Node<E> root) {
        if (root == null) return null;

        //遍历到当前结点（根-左-右 中的根结点），将它的左右结点交换
        Node<E> tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /**
     * 中序实现翻转
     * */
    public Node<E> invertTreeInorder() {
        return invertTreeInorder(root);
    }
    private Node<E> invertTreeInorder(Node<E> root) {
        if (root == null) return null;
        invertTree(root.left);
        Node<E> tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);//这里是的root.left其实是交换之前的right
        return root;
    }

    /**
     * 后序实现翻转
     * */
    public Node<E> invertTreePostorder() {
        return invertTreeInorder(root);
    }
    private Node<E> invertTreePostorder(Node<E> root) {
        if (root == null) return null;
        invertTree(root.left);
        invertTree(root.right);
        Node<E> tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }

    /**
     * 层序实现翻转
     * */
    public Node<E> invertTreeLevelorder() {
        return invertTreeLevelorder(root);
    }
    private Node<E> invertTreeLevelorder(Node<E> root) {
        if (root == null) return root;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            Node<E> tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            //System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }
}
